#include <cassert>
#include <iostream>
#include <cstring>
#include "msfix.h"

using std::cout;
using std::endl;

template<typename T>
class Pool
{
   char** pool;            // Our managed heap (a dynamic array of blocks)
   void* free;             // Pointer to free list
   const size_t elemSize;  // size of objects to manage
   const size_t blockSize; // number of elements in a block of objects
   size_t nBlocks;         // number of blocks allocated (length of heap)
   bool traceFlag;         // Debug trace flag
   
   // Disallow copy and assign
   Pool(const Pool&);
   Pool& operator=(const Pool&);

   // Internal utility functions
   static void storePtr(char* where, char* what)
   {
      // Store a char* (what) in an arbitrary location (where)
      char** loc = reinterpret_cast<char**>(where);
      *loc = what;
   }
   static char* getPtr(char* where)
   {
      // Return the char* stored at an arbitrary location (where)
      char** loc = reinterpret_cast<char**>(where);
      return *loc;
   }
   void link(char* base, size_t nblocks, size_t ncells);
   void expand();

public:
   Pool(size_t blockSize = 100, bool traceFlag = false);
   ~Pool();
   void* allocate();       // Get a pointer to a new object
   void deallocate(void*); // Free an object's slot
   void trace(bool traceFlag)
   {
      this->traceFlag = traceFlag;
   }
};

template<typename T>
Pool<T>::Pool(size_t blockSize, bool traceFlag)
   : elemSize(sizeof(T)), blockSize(blockSize), traceFlag(traceFlag)
{
   // Allocate the initial block
   nBlocks = 0;
   assert(elemSize >= sizeof(char*));
   if (traceFlag)
      cout << "Initializing a pool with element size " << elemSize << " and block size " << blockSize << endl;
   expand();
}

template<typename T>
Pool<T>::~Pool()
{
   if (traceFlag)
      cout << "Deleting " << nBlocks << " blocks\n";
   for (size_t i = 0; i < nBlocks; ++i)
      delete [] pool[i];
   delete [] pool;
}

template<typename T>
void Pool<T>::link(char* base, size_t ncells, size_t elemSize)
{
   if (traceFlag)
      cout << "Linking cells starting at " << static_cast<void*>(base) << endl;
   for (size_t i = 0; i < ncells-1; ++i)
   {
      char* where = base + i*elemSize;
      storePtr(where, where + elemSize);
   }
   char* last = base + elemSize*(ncells-1);
   storePtr(last, 0);
}

template<typename T>
void Pool<T>::expand()
{
   if (traceFlag)
      cout << "Expanding pool...\n";
   
   // Expand pool by 1 block (row)
   char** newPool = new char*[nBlocks+1];
   memcpy(newPool, pool, nBlocks*sizeof(pool[0]));
   delete [] pool;
   pool = newPool;

   // Allocate/initialize the new block
   pool[nBlocks] = new char[blockSize * elemSize];
   link(pool[nBlocks], blockSize, elemSize);
   free = pool[nBlocks++];
}

template<typename T>
void* Pool<T>::allocate()
{
   if (free == 0)
      expand();

   assert(free != 0);
   void* loc = free;
   free = getPtr(static_cast<char*>(free));
   if (traceFlag)
      cout << "Cell allocated at " << loc << endl;
   return loc;
}

template<typename T>
void Pool<T>::deallocate(void* p)
{
   // Prepend p to the free list
   char* where = static_cast<char*>(p);
   storePtr(where, static_cast<char*>(free));
   free = where;
   if (traceFlag)
      cout << "Cell deallocated at " << p << endl;
}
